package msb.class02;

import org.junit.Assert;
import org.junit.Test;
import common.pojo.LinkedNode;
import common.util.ArrayUtil;

import java.util.LinkedList;
import java.util.Stack;


/**
 * 链表实现队列和栈
 */
public class Code04_QueueAndStackForWithChain {


    @Test
    public void testQueue() {
        int[] instant = ArrayUtil.instant(100, 100);
        QueueWithChain queueWithChain = new QueueWithChain();
        LinkedList linkedList = new LinkedList();
        for (int e : instant) {
            queueWithChain.add(e);
            linkedList.add(e);
        }

        for (int e : instant) {
            Integer poll1 = queueWithChain.poll();
            Integer poll2 = (Integer) linkedList.poll();
            Assert.assertEquals(poll1.intValue(), poll2.intValue());
        }
    }

    @Test
    public void testStack() {
        int[] instant = ArrayUtil.instant(100, 100);
        StackWithChain stackWithChain = new StackWithChain();
        Stack stack = new Stack();
        for (int e : instant) {
            stackWithChain.add(e);
            stack.add(e);
        }

        for (int e : instant) {
            Integer poll1 = stackWithChain.pop();
            Integer poll2 = (Integer) stack.pop();
            Assert.assertEquals(poll1.intValue(), poll2.intValue());
        }
    }

    public static class QueueWithChain {
        LinkedNode head;
        LinkedNode tail;
        int size = 0;

        public QueueWithChain() {
        }

        public boolean add(Integer e) {
            LinkedNode current = new LinkedNode();
            current.value = e;
            if (head == null) {
                head = current;
                tail = current;
            } else {
                tail.next = current;
                current.pre = tail;
                tail = current;
            }
            size++;
            return true;
        }

        public Integer poll() {
            System.out.println(size);
            if (size == 0) {
                return null;
            }
            LinkedNode current = head;
            if (size == 1) {
                head = null;
                tail = null;
            } else {
                head = head.next;
                head.pre = null;
            }
            size--;
            return current.value;
        }
    }


    public static class StackWithChain {
        LinkedNode head;
        LinkedNode tail;
        int size = 0;

        public StackWithChain() {
        }

        public boolean add(Integer e) {
            LinkedNode current = new LinkedNode();
            current.value = e;
            if (head == null) {
                head = current;
                tail = current;
            } else {
                tail.next = current;
                current.pre = tail;
                tail = current;
            }
            size++;
            return true;
        }

        public Integer pop() {
            System.out.println(size);
            if (size == 0) {
                return null;
            }
            LinkedNode current = tail;
            if (size == 1) {
                head = null;
                tail = null;
            } else {
                tail = tail.pre;
                tail.next = null;
            }
            size--;
            return current.value;
        }
    }

}
